«
»

Lowest Common Ancestor Code

March 23, 2012, 11:24 pm

Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;


class Node {

public:

  Node() {
  }

  vector<Node *> children;
  Node *parent;
};

Node *make_random_tree(size_t size,Node *root=NULL) {

  if(root == NULL) {
    root = new Node();
  }

  Node *current = root;

  size_t children=rand()%size;
  for(size_t i=0;i<children;i++) {
    Node *nd = new Node();
    nd->parent = current;
    current->children.push_back(nd);
  }

  for(size_t n=0;n<current->children.size();n++) {
    make_random_tree(size-children,current->children[n]);
  }

  return root;
}

Node *get_random(Node *root,size_t avg_size) {

  Node *current = root;
  for(;rand()%(avg_size*2) != 0;) {
    if(current->children.size() == 0) return current;

    current = current->children[rand()%current->children.size()];
  }

  return current;
}

Node * get_next_child(Node *node,Node *child) {

  bool next=false;
  for(size_t n=0;n<node->children.size();n++) {

    if(next==true) {
      return node->children[n];
    }

    if(node->children[n] == child) next=true;
  }

  return NULL;
}

vector<Node *> get_path(Node *root,Node *n) {

  vector<Node *> current_path;
  current_path.push_back(root);

  if(n==root) return current_path;

  Node *current_child = root->children[0];

  for(;;) {

    current_path.push_back(current_child);
    if(current_child == n) return current_path;

    if(current_child->children.size() != 0) {
      current_path.push_back(current_child->children[0]);
      current_child = current_child->children[0];
    } else {
      current_child = NULL;
      for(;current_child == NULL;) {
        Node *old_child = current_path[current_path.size()-1];
        current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
        current_child = get_next_child(current_path[current_path.size()-1],old_child);

        if(old_child==root) { return vector<Node *>(); }
      }
    }
  }

  // Should never get here
  return vector<Node *>();
}

vector<Node *> get_path_parent(Node *root,Node *n) {

  vector<Node *> v;

  for(Node *current = n;current != root;current = current->parent) {
    v.push_back(current);
  }
  v.push_back(root);

  reverse(v.begin(),v.end());

  return v;
}

Node *find_lca_parent(Node *root,Node *n1,Node *n2) {

  vector<Node *> path1 = get_path_parent(root,n1);
  vector<Node *> path2 = get_path_parent(root,n2);

  for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
  for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;

  size_t shortest_path_length;
  if(path1.size() < path2.size()) shortest_path_length = path1.size();
                             else shortest_path_length = path2.size();

  size_t n;
  for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);

  return path1[n-1];
}

Node *find_lca(Node *root,Node *n1,Node *n2) {

  vector<Node *> path1 = get_path(root,n1);
  vector<Node *> path2 = get_path(root,n2);

  size_t shortest_path_length;
  if(path1.size() < path2.size()) shortest_path_length = path1.size();
                             else shortest_path_length = path2.size();

  size_t n;
  for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);

  return path1[n-1];
}

int main() {

  Node *root = make_random_tree(100);

  Node *n1 = get_random(root,20);
  Node *n2 = get_random(root,20);

  Node *lca1a = find_lca_parent(root,n1,n2);
  Node *lca1b = find_lca       (root,n1,n2);

  cout << "LCA1-a: " << lca1a << endl;
  cout << "LCA1-b: " << lca1a << endl;

  Node *n3 = root->children[0]->children[0]->children[0];
  Node *n4 = root->children[0]->children[0]->children[1];
  Node *lca2a = find_lca_parent(root,n3,n4);
  Node *lca2b = find_lca       (root,n3,n4);

  cout << "LCA2-a: " << lca2a << endl;
  cout << "LCA2-b: " << lca2b << endl;
}
Category: Uncategorized  |  Comment (RSS)  |  Trackback

Leave a Reply